package com.wanghe.leetcode.jianzhioffer;

import java.util.HashMap;
import java.util.Map;

/**
 * 面试题 01.04. 回文排列
 * https://leetcode-cn.com/problems/palindrome-permutation-lcci/
 */
public class Problem0104 {

    public static void main(String[] args) {
        String s = "tactcoa";
        System.out.println(canPermutePalindrome(s));
    }

    private static boolean canPermutePalindrome(String s) {
        if (null == s || s.isEmpty() || 1 == s.length()) {
            return true;
        }
        Map<Character, Long> charFreq = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Long l = charFreq.get(c);
            if (null == l) {
                l = 1L;
            } else {
                l++;
            }
            charFreq.put(c, l);
        }
        long oddCount = 0L;
        for (char c : charFreq.keySet()) {
            Long freq = charFreq.get(c);
            if (freq % 2 != 0) {
                oddCount++;
                if (oddCount > 1) {
                    return false;
                }
            }
        }

        return true;
    }

}
